class Node:

    def __init__(self, value, next_node=None):
        self.data = value
        self._next = next_node


class SinglyLinkedList:

    def __init__(self):
        self._head = None

    def find_by_index(self, index: int):
        p = self._head
        i = 0
        while p and i != index:
            p = p._next
            i += 1
        if not p:
            return
        return p

    def find_by_value(self, value):
        if not self._head or not value:
            return
        p = self._head
        while p and p.data != value:
            p = p._next
        if not p:
            return
        return p

    def insert_node_to_head(self, new_node: Node):
        if not new_node:
            return
        new_node._next = self._head
        self._head = new_node

    def insert_value_to_head(self, value):
        new_node = Node(value)
        self.insert_node_to_head(new_node)

    def insert_node_after(self, node: Node, new_node: Node):
        if not new_node or not node:
            return
        new_node._next = node._next
        node._next = new_node

    def insert_value_after(self, node: Node, value):
        new_node = Node(value)
        self.insert_node_after(node, new_node)

    def insert_node_before(self, node: Node, new_node: Node):
        if not self._head or not node or not new_node:
            return
        p = self._head
        if p == node:
            self.insert_node_to_head(new_node)
            return
        while p._next and p._next != node:
            p = p._next
        if not p._next:
            return
        new_node._next = node
        p._next = new_node

    def insert_value_before(self, node: Node, value):
        new_node = Node(value)
        self.insert_node_before(node, new_node)

    def delete_by_node(self, node: Node):
        if not self._head or not node:
            return
        if self._head == node:
            self._head = self._head._next
            return
        p = self._head
        while p and p._next != node:
            p = p._next
        if not p:
            return
        p._next = p._next._next

    def delete_by_value(self, value):
        if not self._head:
            return
        if self._head.data == value:
            self._head = self._head._next
            return
        p = self._head
        while p and p._next.data != value:
            p = p._next
        if not p:
            return
        p._next = p._next._next

    def delete_last_n_node(self, n):
        """删除链表中倒数第N个节点.
        主体思路：
            设置快、慢两个指针，快指针先行，慢指针不动；当快指针跨了N步以后，快、慢指针同时往链表尾部移动，
            当快指针到达链表尾部的时候，慢指针所指向的就是链表的倒数第N个节点
        参数:
            n:需要删除的倒数第N个序数
        """
        fast = self._head
        slow = self._head
        step = 0

        while step <= n:
            fast = fast.next_node
            step += 1

        while fast.next_node is not None:
            tmp = slow
            fast = fast.next_node
            slow = slow.next_node

        tmp.next_node = slow.next_node

    def find_mid_node(self):
        """查找链表中的中间节点.
        主体思想:
            设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，则当快指针到达链表尾部的时候，慢指针指向链表的中间节点
        返回:
            node:链表的中间节点
        """
        fast = self._head
        slow = self._head

        while fast.next_node is not None:
            fast = fast.next_node.next_node
            slow = slow.next_node

        return slow

    def reversed_self(self):
        """翻转链表自身."""
        if self._head is None or self._head._next is None:  # 如果链表为空，或者链表只有一个节点
            return

        pre = self._head
        node = self._head._next
        while node is not None:
            pre, node = self.__reversed_with_two_node(pre, node)

        self._head._next = None
        self._head = pre

    def __reversed_with_two_node(self, pre, node):
        """翻转相邻两个节点.
        参数:
            pre:前一个节点
            node:当前节点
        返回:
            (pre,node):下一个相邻节点的元组
        """
        tmp = node._next
        node._next = pre
        pre = node  # 这样写有点啰嗦，但是能让人更能看明白
        node = tmp
        return pre, node

    def has_ring(self):
        """检查链表中是否有环.
        主体思想：
            设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，如果快指针没有与慢指针相遇而是顺利到达链表尾部
            说明没有环；否则，存在环
        返回:
            True:有环
            False:没有环
        """
        fast = self._head
        slow = self._head

        while (fast.next_node is not None) and (fast is not None):
            fast = fast.next_node.next_node
            slow = slow.next_node
            if fast == slow:
                return True

        return False

    def __repr__(self):
        result = []
        p = self._head
        while p:
            result.append(str(p.data))
            p = p._next
        return '->'.join(result)

    def __iter__(self):
        p = self._head
        while p:
            yield p.data
            p = p._next

    def fun(self):
        cur = self._head
        pre = None
        while cur:
            cur._next, pre, cur = pre, cur, cur._next
        i = 1
        while i != 4:
            pre = pre._next
            i += 1
        return pre.data


if __name__ == '__main__':
    l = SinglyLinkedList()
    for i in range(10):
        l.insert_value_to_head(i)
    l.insert_value_before(l.find_by_value(8), 11)
    print('l is:%s' % l)
    l.reversed_self()
    print(l)
    print(l.fun())